package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/8/6 17:30
 */
public class Title1545 {


    /**
     *  * S1 = "0"
     *   当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
     * @param n
     * @param k
     * @return
     */
    public static char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }
        //中间"1"为第几位数  第n项时，长度为2**n -1   前半段长度 2**(n-1)-1  1  2**(n-1)-1
        int mid = 1 << (n - 1);
        if (k == mid) {
            return '1';
        }else if (k < mid) {
            return findKthBit(n - 1, k);
        }else{
            // 2**n - k
            k = mid * 2 - k;
            return findKthBit(n - 1, k) == '1' ? '0' : '1';
        }
    }


    public static void main(String[] args) {
        findKthBit(3, 1);
    }
}
